package com.wyw.leetcode.learning.simple;

import java.util.*;

/**
 * leetcode topic 387
 *  字符串中第一个唯一字符
 *      给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/28 9:50
 */
public class Topic387 {

    public static void main(String[] args) {

//        String s = "leetcode";
//        String s = "loveleetcode";
        String s = "aabb";
        System.out.println(firstUniqChar(s));
        System.out.println(firstUniqChar1(s));


    }

    /**
     * 哈希表
     * @param s
     * @return
     */
    public static int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        List<Character> list = new ArrayList();
        for(char c: s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            list.add(c);
        }

        for(int i = 0; i < list.size(); i++) {
            Character c = list.get(i);

            if(map.get(c) == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * @param s
     * @return
     */
    public static int firstUniqChar1(String s) {
        Map<Character, Integer> frequency = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;

    }

    /**
     * 哈希表存索引
     * @param s
     * @return
     */
    public static int firstUniqChar2(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (position.containsKey(ch)) {
                position.put(ch, -1);
            } else {
                position.put(ch, i);
            }
        }
        int first = n;
        for (Map.Entry<Character, Integer> entry : position.entrySet()) {
            int pos = entry.getValue();
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        if (first == n) {
            first = -1;
        }
        return first;


    }

    /**
     * 队列
     * @param s
     * @return
     */
    public static int firstUniqChar3(String s) {
        Map<Character, Integer> position = new HashMap<>();
        Queue<Pair> queue = new LinkedList<>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                position.put(ch, -1);
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().pos;
    }

    public static class Pair {
        char ch;
        int pos;

        public Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }

        Pair() {

        }
    }


    public int firstUniqChar_2(String s) {
        int[] freq = new int[26];
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            freq[ch - 'a']++;
        }
        for (int i = 0; i < chars.length; i++) {
            if (freq[chars[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

}



